Circulant matrix

 ( Numerical Linear Algebra ) 

In linear algebra, a circulant matrix is a square matrix in which all rows are composed of the same elements and each row is rotated one element to the right relative to the preceding row. It is a particular kind of Toeplitz matrix.

In numerical analysis, circulant matrices are important because they are diagonalized by a discrete Fourier transform, and hence that contain them may be quickly solved using a fast Fourier transform.

They can be interpreted analytically as the integral kernel of a convolution operator on the cyclic group $C\_n$ and hence frequently appear in formal descriptions of spatially invariant linear operations. This property is also critical in modern software defined radios, which utilize Orthogonal Frequency Division Multiplexing to spread the symbols (bits) using a cyclic prefix. This enables the channel to be represented by a circulant matrix, simplifying channel equalization in the frequency domain.

In cryptography, a circulant matrix is used in the MixColumns step of the Advanced Encryption Standard.

---

Definition An $n\; \backslash times\; n$ circulant matrix $C$ takes the form or the transpose of this form (by choice of notation). If each $c\_i$ is a $p\; \backslash times\; p$ square matrix, then the $np\; \backslash times\; np$ matrix $C$ is called a block-circulant matrix.

A circulant matrix is fully specified by one vector, $c$, which appears as the first column (or row) of $C$. The remaining columns (and rows, resp.) of $C$ are each cyclic permutations of the vector $c$ with offset equal to the column (or row, resp.) index, if lines are indexed from $0$ to $n-1$. (Cyclic permutation of rows has the same effect as cyclic permutation of columns.) The last row of $C$ is the vector $c$ shifted by one in reverse.

Different sources define the circulant matrix in different ways, for example as above, or with the vector $c$ corresponding to the first row rather than the first column of the matrix; and possibly with a different direction of shift (which is sometimes called an anti-circulant matrix).

The polynomial $f(x)\; =\; c\_0\; +\; c\_1\; x\; +\; \backslash dots\; +\; c\_\{n-1\}\; x^\{n-1\}$ is called the associated polynomial of the matrix $C$.

---

Properties

---

Eigenvectors and eigenvalues The normalized of a circulant matrix are the Fourier modes, namely, $$v\_j=\backslash frac\{1\}\{\backslash sqrt\{n\}\}\; \backslash left(1,\; \backslash omega^j,\; \backslash omega^\{2j\},\; \backslash ldots,\; \backslash omega^\{(n-1)j\}\backslash right)^\{T\},\backslash quad\; j\; =\; 0,\; 1,\; \backslash ldots,\; n-1,$$ where $\backslash omega=\backslash exp\; \backslash left(\backslash tfrac\{2\backslash pi\; i\}\{n\}\backslash right)$ is a primitive $n$-th root of unity and $i$ is the imaginary unit.

(This can be understood by realizing that multiplication with a circulant matrix implements a convolution. In Fourier space, convolutions become multiplication. Hence the product of a circulant matrix with a Fourier mode yields a multiple of that Fourier mode, i.e. it is an eigenvector.)

The corresponding are given by $$\backslash lambda\_j\; =\; c\_0+c\_\{1\}\; \backslash omega^\{-j\}\; +\; c\_\{2\}\; \backslash omega^\{-2j\}\; +\; \backslash dots\; +\; c\_\{n-1\}\; \backslash omega^\{-(n-1)j\},\backslash quad\; j\; =\; 0,\; 1,\; \backslash dots,\; n-1.$$

---

Determinant As a consequence of the explicit formula for the eigenvalues above, the determinant of a circulant matrix can be computed as: $$\backslash det\; C\; =\; \backslash prod\_\{j=0\}^\{n-1\}\; (c\_0\; +\; c\_\{n-1\}\; \backslash omega^j\; +\; c\_\{n-2\}\; \backslash omega^\{2j\}\; +\; \backslash dots\; +\; c\_1\backslash omega^\{(n-1)j\}).$$ Since taking the transpose does not change the eigenvalues of a matrix, an equivalent formulation is $$\backslash det\; C\; =\; \backslash prod\_\{j=0\}^\{n-1\}\; (c\_0\; +\; c\_1\; \backslash omega^j\; +\; c\_2\; \backslash omega^\{2j\}\; +\; \backslash dots\; +\; c\_\{n-1\}\backslash omega^\{(n-1)j\})\; =\; \backslash prod\_\{j=0\}^\{n-1\}\; f(\backslash omega^j).$$

---

Rank The rank of a circulant matrix $C$ is equal to $n\; -\; d$ where $d$ is the degree of the polynomial $\backslash gcd(\; f(x),\; x^n\; -\; 1)$.

---

Other properties

• Any circulant is a matrix polynomial (namely, the associated polynomial) in the cyclic permutation matrix $P$: $$C\; =\; c\_0\; I\; +\; c\_1\; P\; +\; c\_2\; P^2\; +\; \backslash dots\; +\; c\_\{n-1\}\; P^\{n-1\}\; =\; f(P),$$ where $P$ is given by the companion matrix $$P\; =\; \backslash begin\{bmatrix\}$$

0&0&\cdots&0&1\\
1&0&\cdots&0&0\\
0&\ddots&\ddots&\vdots&\vdots\\
\vdots&\ddots&\ddots&0&0\\
0&\cdots&0&1&0
     

\end{bmatrix}.

• The set of $n\; \backslash times\; n$ circulant matrices forms an $n$-dimensional vector space with respect to addition and scalar multiplication. This space can be interpreted as the space of functions on the cyclic group of order $n$, $C\_n$, or equivalently as the group ring of $C\_n$.
• Circulant matrices form a commutative algebra, since for any two given circulant matrices $A$ and $B$, the sum $A\; +\; B$ is circulant, the product $AB$ is circulant, and $AB\; =\; BA$.
• For a nonsingular circulant matrix $A$, its inverse matrix $A^\{-1\}$ is also circulant. For a singular circulant matrix, its Moore–Penrose pseudoinverse $A^+$ is circulant.
• The discrete Fourier transform matrix of order $n$ is defined as by

$$F\_n\; =\; (f\_\{jk\})\; \backslash text\{\; with\; \}\; f\_\{jk\}\; =\; e^\{-2\backslash pi\; i/n\; \backslash cdot\; jk\},\; \backslash ,\backslash text\{for\; \}\; 0\; \backslash leq\; j,k\; \backslash leq\; n-1.$$ There are important connections between circulant matrices and the DFT matrices. In fact, it can be shown that $$C\; =\; F\_n^\{-1\}\backslash operatorname\{diag\}(F\_n\; c)\; F\_n\; ,$$ where $c$ is the first column of $C$. The eigenvalues of $C$ are given by the product $F\_n\; c$. This product can be readily calculated by a fast Fourier transform.

• Let $p(x)$ be the (monic polynomial) characteristic polynomial of an $n\; \backslash times\; n$ circulant matrix $C$. Then the scaled derivative $\backslash frac\{1\}\{n\}p\text{'}(x)$ is the characteristic polynomial of the following $(n-1)\backslash times(n-1)$ submatrix of $C$: $$C\_\{n-1\}\; =\; \backslash begin\{bmatrix\}$$

c_0     & c_{n-1} & \cdots  & c_3     & c_2     \\
c_1     & c_0     & c_{n-1} &         & c_3     \\
\vdots  & c_1     & c_0     & \ddots  & \vdots  \\
c_{n-3} &         & \ddots  & \ddots  & c_{n-1} \\
c_{n-2} & c_{n-3} & \cdots  & c_{1}   & c_0     \\
     

\end{bmatrix} (see for the proof).

---

Analytic interpretation Circulant matrices can be interpreted geometry, which explains the connection with the discrete Fourier transform.

Consider vectors in $\backslash R^n$ as functions on the with period $n$, (i.e., as periodic bi-infinite sequences: $\backslash dots,a\_0,a\_1,\backslash dots,a\_\{n-1\},a\_0,a\_1,\backslash dots$) or equivalently, as functions on the cyclic group of order $n$ (denoted $C\_n$ or $\backslash Z/n\backslash Z$) geometrically, on (the vertices of) the regular polygon: this is a discrete analog to periodic functions on the real line or circle.

Then, from the perspective of operator theory, a circulant matrix is the kernel of a discrete integral transform, namely the convolution operator for the function $(c\_0,c\_1,\backslash dots,c\_\{n-1\})$; this is a discrete circular convolution. The formula for the convolution of the functions $(b\_i)\; :=\; (c\_i)\; *\; (a\_i)$ is

$b\_k\; =\; \backslash sum\_\{i=0\}^\{n-1\}\; a\_i\; c\_\{k-i\}$

(recall that the sequences are periodic) which is the product of the vector $(a\_i)$ by the circulant matrix for $(c\_i)$.

The discrete Fourier transform then converts convolution into multiplication, which in the matrix setting corresponds to diagonalization.

The $C^*$-algebra of all circulant matrices with complex number entries is isomorphic to the group $C^*$-algebra of $\backslash Z/n\backslash Z.$

---

Symmetric circulant matrices For a symmetric matrix circulant matrix $C$ one has the extra condition that $c\_\{n-i\}=c\_i$. Thus it is determined by $\backslash lfloor\; n/2\backslash rfloor\; +\; 1$ elements.

The eigenvalues of any real number symmetric matrix are real. The corresponding eigenvalues $\backslash vec\{\backslash lambda\}=\; \backslash sqrt\; n\; \backslash cdot\; F\_n^\{\backslash dagger\}\; c$ become: for $n$ even, and

& = & c_0 + 2 c_1 \Re \omega_k + 2 c_2 \Re \omega_k^2 + \dots + 2c_{(n-1)/2} \Re \omega_k^{(n-1)/2} \end{array}
     

for $n$ odd, where $\backslash Re\; z$ denotes the complex number of $z$. This can be further simplified by using the fact that $\backslash Re\; \backslash omega\_k^j\; =\; \backslash Re\; e^\{-\backslash frac\{2\backslash pi\; i\}\{n\}\; \backslash cdot\; kj\}\; =\; \backslash cos(-\backslash frac\{2\backslash pi\}\{n\}\; \backslash cdot\; kj)$ and $\backslash omega\_k^\{n/2\}=e^\{-\backslash frac\{2\backslash pi\; i\}\{n\}\; \backslash cdot\; k\; \backslash frac\{n\}\{2\}\}\; =e^\{-\backslash pi\; i\; \backslash cdot\; k\}$ depending on $k$ even or odd.

Symmetric circulant matrices belong to the class of bisymmetric matrices.

---

Hermitian circulant matrices The complex version of the circulant matrix, ubiquitous in communications theory, is usually Hermitian matrix. In this case $c\_\{n-i\}\; =\; c\_i^*,\; \backslash ;\; i\; \backslash le\; n/2$ and its determinant and all eigenvalues are real.

If n is even the first two rows necessarily takes the form in which the first element $r\_3$ in the top second half-row is real.

If n is odd we get

Tee has discussed constraints on the eigenvalues for the Hermitian condition.

---

Applications

---

In linear equations Given a matrix equation

$C\; \backslash mathbf\{x\}\; =\; \backslash mathbf\{b\},$

where $C$ is a circulant matrix of size $n$, we can write the equation as the circular convolution $$\backslash mathbf\{c\}\; \backslash star\; \backslash mathbf\{x\}\; =\; \backslash mathbf\{b\},$$ where $\backslash mathbf\; c$ is the first column of $C$, and the vectors $\backslash mathbf\; c$, $\backslash mathbf\; x$ and $\backslash mathbf\; b$ are cyclically extended in each direction. Using the circular convolution theorem, we can use the discrete Fourier transform to transform the cyclic convolution into component-wise multiplication $$\backslash mathcal\{F\}\_\{n\}(\backslash mathbf\{c\}\; \backslash star\; \backslash mathbf\{x\})\; =\; \backslash mathcal\{F\}\_\{n\}(\backslash mathbf\{c\})\; \backslash mathcal\{F\}\_\{n\}(\backslash mathbf\{x\})\; =\; \backslash mathcal\{F\}\_\{n\}(\backslash mathbf\{b\})$$ so that $$\backslash mathbf\{x\}\; =\; \backslash mathcal\{F\}\_n^\{-1\}\; \backslash left[\; \backslash left(\; \backslash right)\_\{\backslash !\backslash nu\backslash in\backslash Z\}\backslash ,\; \backslash right]^\{\backslash rm\; T\}.$$

This algorithm is much faster than the standard Gaussian elimination, especially if a fast Fourier transform is used.

---

In graph theory In graph theory, a graph or directed graph whose adjacency matrix is circulant is called a circulant graph/digraph. Equivalently, a graph is circulant if its automorphism group contains a full-length cycle. The Möbius ladders are examples of circulant graphs, as are the for fields of prime number order.

---

External links

• IPython Notebook demonstrating properties of circulant matrices

Post Comment